1. Field of Invention
The present invention relates generally to methods, apparatus, and systems for manipulating data structures in a computing system. More particularly, the present invention relates to adding data on a circular, singly linked list.
2. Description of the Related Art
Linked lists are well known in the art, and various methods have been employed to manipulate linked lists. Linked lists are one of the most common data structures employed for the manipulation of data. Linked lists are particularly important with an operating system. Operating systems control a variety of resources simultaneously. A linked list might be used, for example, to hold requests for each individual resource. Circular linked lists can also be used in a server-client environment where the server uses the circular linked list to record those clients that are waiting for service at a particular time. By using the circular linked list, a server can insure that its attention is evenly distributed amongst the waiting clients by visiting and servicing each waiting client as it circulates around the list. Using a consumer/producer model to visualize the linked list, the server can be considered the consumer and the clients each representing a producer as illustrated in FIG. 1 that shows a linked list 100 representing individual work queues (WQ). As shown in FIG. 1, a producer adds work queues with new work to the list 100 as a consumer continually scans the list, processing packets from each work queue in turn and deletes a work queue when it's packets are spent. Using this arrangement, the list 100 contains all work queues that are pending where they remain so long as they still have work (or packets to transmit) until it is ultimately deleted when the work (or packet) has been depleted.
Generally, linked lists can take two forms: (1) circular singly linked lists; or (2) circular doubly linked lists. With a singly linked list, each member contains a field pointing to the next member while doubly linked lists add a second pointer to each member that points to the previous member. Although doubly linked lists facilitate scanning in the reverse direction, they are more difficult to maintain since the additional pointers require additional write operations to SRAM substantially increasing cycle time over singly linked lists.
Conventionally, additions to a linked list require at least 3 SRAM accesses an example of which is illustrated in FIGS. 2A-2C showing a conventional approach to adding a new member to a circular singly linked list 200 having a number of entries 201. Assuming, for example, that an entry 201-3 is to be added between an entry 201-2 and an entry 201-4. As shown, the entry 201-2 has a next pointer field 202-2 that points to the entry 201-4 which, in turn, has a next pointer field 202-4 which points to a next entry 201-1. During the conventional addition operation, (as shown in FIG. 2B) the contents of the next pointer field 202-2 are copied to a next pointer field 202-3 associated with the added entry 201-3 such that the entry 201-3 now points to the entry 201-4. Finally as shown in FIG. 2C, the next pointer field 202-2 (associated with the entry 201-2) is updated such that the entry 201-2 points to the added entry 201-3 thereby completing the addition operation. Since accesses to the same SRAM can not generally be parallelized, it is important for performance reasons to keep the number of reads and writes to memory at a minimum. Although registers can be accessed in parallel they do not have the density of SRAM.
Unfortunately, however, the conventional approach to adding entries to a circular singly linked list is wasteful of memory resources since the accesses to the SRAM cannot be parallelized using a single SRAM and adding additional SRAM resources is costly and inefficient.
Therefore, what is desired is a method, apparatus, and system for efficiently adding a entry in an arbitrary (i.e., unspecified) location in a circular singly linked list.